import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2023-01-05
 * Time: 16:35
 */


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


// https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
public class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer, ListNode> map = new HashMap<>();
        ListNode headNode = new ListNode(0, head);
        ListNode cur = head;
        map.put(0, headNode);
        int sum = 0;
        while (cur != null) {
            sum += cur.val;
            if (map.containsKey(sum)) {
                // 将存在重复值中间的所有元素删除
                ListNode node = map.get(sum);
                ListNode delete = node.next;
                node.next = cur.next;

                // 删除哈希表两个重复值中间的全部key
                // 拷贝一份sum
                int sumCopy = sum;
                while (delete.next != cur.next) {
                    sumCopy += delete.val;
                    map.remove(sumCopy);
                    delete = delete.next;
                }
            } else {
                map.put(sum, cur);
            }
            cur = cur.next;
        }
        return headNode.next;
    }
}
